package com.dyz.leetcode._09_heapAndPriorityQueue;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class _973_kClosest {
    //基于排序
    public int[][] kClosest(int[][] points, int k) {
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return (o1[0] * o1[0] + o1[1] * o1[1]) - (o2[0] * o2[0] + o2[1] * o2[1]);
            }
        });

        return Arrays.copyOf(points, k);

    }

    //基于优先队列
    public int[][] kClosest1(int[][] points, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(k + 1, (o2, o1) -> (o1[0] * o1[0] + o1[1] * o1[1]) - (o2[0] * o2[0] + o2[1] * o2[1]));

        for (int[] point : points) {
            pq.add(point);
            if (pq.size() > k) {
                pq.remove();
            }
        }
        //小顶堆中存储的就是出现了前k个高频的元素
        int[][] res = new int[k][2];
        int index = 0;
        while (!pq.isEmpty()) {
            res[index++] = pq.remove();

        }
        return res;
    }
}

